树链剖分

树链剖分就是对一棵树分成几条链，把树形变为线性，减少处理难度
需要处理的问题：

将树从x到y结点最短路径上所有节点的值都加上z
求树从x到y结点最短路径上所有节点的值之和
将以x为根节点的子树内所有节点值都加上z
求以x为根节点的子树内所有节点值之和

概念

重儿子：对于每一个非叶子节点，它的儿子中以那个儿子为根的子树节点数最大的儿子为该节点的重儿子 (Ps: 感谢@shzr大佬指出我此句话的表达不严谨qwq, 已修改)
轻儿子：对于每一个非叶子节点，它的儿子中非重儿子的剩下所有儿子即为轻儿子
叶子节点没有重儿子也没有轻儿子（因为它没有儿子。。）
重边：连接任意两个重儿子的边叫做重边
轻边：剩下的即为轻边
重链：相邻重边连起来的连接一条重儿子的链叫重链对于叶子节点，若其为轻儿子，则有一条以自己为起点的长度为1的链每一条重链以轻儿子为起点

dfs1()

这个dfs要处理几件事情：

标记每个点的深度dep[]
标记每个点的父亲fa[]
标记每个非叶子节点的子树大小(含它自己)
标记每个非叶子节点的重儿子编号son[]

inline void dfs1(int x,int f,int deep){//x当前节点，f父亲，deep深度 
    dep[x]=deep;//标记每个点的深度 
    fa[x]=f;//标记每个点的父亲 
    siz[x]=1;//标记每个非叶子节点的子树大小 
    int maxson=-1;//记录重儿子的儿子数 
    for(Rint i=beg[x];i;i=nex[i]){
        int y=to[i];
        if(y==f)continue;//若为父亲则continue 
        dfs1(y,x,deep+1);//dfs其儿子 
        siz[x]+=siz[y];//把它的儿子数加到它身上 
        if(siz[y]>maxson)son[x]=y,maxson=siz[y];//标记每个非叶子节点的重儿子编号 
    }
}//变量解释见最下面

dfs2()

这个dfs2也要预处理几件事情

标记每个点的新编号
赋值每个点的初始值到新编号上
处理每个点所在链的顶端
处理每条链

顺序：先处理重儿子再处理轻儿子，理由后面说

inline void dfs2(int x,int topf){//x当前节点，topf当前链的最顶端的节点 
    id[x]=++cnt;//标记每个点的新编号 
    wt[cnt]=w[x];//把每个点的初始值赋到新编号上来 
    top[x]=topf;//这个点所在链的顶端 
    if(!son[x])return;//如果没有儿子则返回 
    dfs2(son[x],topf);//按先处理重儿子，再处理轻儿子的顺序递归处理 
    for(Rint i=beg[x];i;i=nex[i]){
        int y=to[i];
        if(y==fa[x]||y==son[x])continue;
        dfs2(y,y);//对于每一个轻儿子都有一条从它自己开始的链 
    }
}//变量解释见最下面

处理问题

Attention 重要的来了！！！
前面说到dfs2的顺序是先处理重儿子再处理轻儿子
我们来模拟一下：

因为顺序是先重再轻，所以每一条重链的新编号是连续的
因为是dfs，所以每一个子树的新编号也是连续的

现在回顾一下我们要处理的问题

处理任意两点间路径上的点权和
处理一点及其子树的点权和
修改任意两点间路径上的点权
修改一点及其子树的点权

1、当我们要处理任意两点间路径时：
设所在链顶端的深度更深的那个点为x点

ans加上x点到x所在链顶端这一段区间的点权和
把x跳到x所在链顶端的那个点的上面一个点

不停执行这两个步骤，直到两个点处于一条链上，这时再加上此时两个点的区间和即可

这时我们注意到，我们所要处理的所有区间均为连续编号(新编号)，于是想到线段树，用线段树处理连续编号区间和
每次查询时间复杂度为

$O(log^2n)$

inline int qRange(int x,int y){
    int ans=0;
    while(top[x]!=top[y]){//当两个点不在同一条链上 
        if(dep[top[x]]<dep[top[y]])swap(x,y);//把x点改为所在链顶端的深度更深的那个点
        res=0;
        query(1,1,n,id[top[x]],id[x]);//ans加上x点到x所在链顶端 这一段区间的点权和
        ans+=res;
        ans%=mod;//按题意取模 
        x=fa[top[x]];//把x跳到x所在链顶端的那个点的上面一个点
    }
    //直到两个点处于一条链上
    if(dep[x]>dep[y])swap(x,y);//把x点深度更深的那个点
    res=0;
    query(1,1,n,id[x],id[y]);//这时再加上此时两个点的区间和即可
    ans+=res;
    return ans%mod;
}//变量解释见最下面

2、处理一点及其子树的点权和：
想到记录了每个非叶子节点的子树大小(含它自己)，并且每个子树的新编号都是连续的
于是直接线段树区间查询即可
时间复杂度为O(logn)O(log⁡n)

inline int qSon(int x){
    res=0;
    query(1,1,n,id[x],id[x]+siz[x]-1);//子树区间右端点为id[x]+siz[x]-1 
    return res;
}

当然，区间修改就和区间查询一样的啦~~

inline void updRange(int x,int y,int k){
    k%=mod;
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]])swap(x,y);
        update(1,1,n,id[top[x]],id[x],k);
        x=fa[top[x]];
    }
    if(dep[x]>dep[y])swap(x,y);
    update(1,1,n,id[x],id[y],k);
}
 
inline void updSon(int x,int k){
    update(1,1,n,id[x],id[x]+siz[x]-1,k);
}//变量解释见最下面

MD:

1. #include <cstdio>
2. #include <cstdlib>
3. #include <algorithm>
4. #include <iostream>
5. #define maxn 100005
6. #define ll long long
7. #define ls(x) ((x)<<1)
8. #define rs(x) ((x)<<1|1)
9. #define pushup(x) tree[(x)] = tree[ls((x))] + tree[rs((x))]
10. ll dep[maxn] , f[maxn] , sz[maxn] , n , head[maxn] , idx[maxn] , val[maxn] , hs[maxn] , m , r , p , cnt , tot , v[maxn] , top[maxn] , tree[maxn<<2] , tag[maxn<<2];
11. struct edge{
12.     ll next , to;
13. }e[maxn*2];
14. void dfs1(ll x , ll fx);//f[],sz[],dep[],hs[]
15. void dfs2(ll x , ll topV);
16. inline void add(ll x , ll y);
17. ll query(ll L , ll R , ll l , ll r , ll node);
18. void update(ll L , ll R , ll l , ll r , ll node , ll val);
19. inline void pushdown(ll node , ll ln , ll rn);
20. ll qLink(ll x , ll y);// problem request
21. void updLink(ll x ,ll y , ll v);//preblem request
22. ll qST(ll x);//preblem request
23. void updST(ll x , ll v);//preblem request
24. void build(ll l , ll r , ll node);
25. int main()
26. {
27.     scanf("%lld%lld%lld%lld",&n,&m,&r,&p);
28.     ll x , y , d;
29.     for(int i = 1 ; i <= n ; ++i)
30.         scanf("%lld",&val[i]);
31.     for(int i = 1 ; i <= n-1 ; ++i)
32.     {
33.         scanf("%lld%lld",&x,&y);
34.         add(x,y) , add(y,x);
35.     }
36.     // puts("OK");
37.     dfs1(r,r);
38.     // puts("OK");
39.     dfs2(r,r);//root link topv is itself
40.     // puts("OK");
41.     build(1,n,1);
42.     // puts("OK");
43.     ll op , xx , yy , zz;
44.     for(int i = 1 ; i <= m ; ++i)
45.     {
46.         scanf("%lld",&op);
47.         if(op == 1) scanf("%lld%lld%lld",&xx,&yy,&zz) , updLink(xx,yy,zz);
48.         else if(op == 2) scanf("%lld%lld",&xx,&yy) , printf("%lld\n",qLink(xx,yy));
49.         else if(op == 3) scanf("%lld%lld",&xx,&zz) , updST(xx,zz);
50.         else scanf("%lld",&xx) , printf("%lld\n",qST(xx));
51.     }
52. }
53. inline void add(ll x , ll y)
54. {
55.     e[++cnt].next = head[x];
56.     e[cnt].to = y;
57.     head[x] = cnt;
58. }
59. ll qLink(ll x , ll y)
60. {
61.     ll ans = 0;
62.     while(top[x] != top[y])
63.     {
64.         if(dep[top[x]] < dep[top[y]]) std::swap(x,y);
65.         ans += query(idx[top[x]] , idx[x] , 1 , n , 1) % p , ans %= p;
66.         x = f[top[x]];
67.     }
68.     if(dep[x] < dep[y]) std::swap(x,y);
69.     ans += query(idx[y],idx[x],1,n,1);
70.     return ans % p;
71. }
72. void updLink(ll x , ll y , ll v)
73. {
74.     while(top[x] != top[y])
75.     {
76.         if(dep[top[x]] < dep[top[y]]) std::swap(x,y);
77.         update(idx[top[x]] , idx[x] , 1 , n , 1 , v);
78.         x = f[top[x]];
79.     }
80.     if(dep[x] > dep[y]) std::swap(x,y);
81.     update(idx[x] , idx[y] , 1 , n , 1 , v);
82. }
83. ll qST(ll x)
84. {
85.     ll ans = query(idx[x] , idx[x] + sz[x] - 1 , 1 , n , 1) % p;
86.     return ans;
87. }
88. void updST(ll x , ll v)
89. {
90.     update(idx[x] , idx[x] + sz[x] - 1 , 1 , n , 1 , v);
91. }
92. void dfs1(ll x , ll fx)
93. {
94.     f[x] = fx;
95.     dep[x] = dep[fx] + 1;
96.     sz[x] = 1;
97.     ll maxx = -1 ;
98.     for(ll i = head[x] ; i ; i = e[i].next)
99.         if(e[i].to != fx)
100.             dfs1(e[i].to,x) , sz[x] += sz[e[i].to];//dfs1(e[i].to,x)  not dfs1(e[i].to,fx)!!!!!!!!!!!!!!
101.     for(int i = head[x] ; i ; i = e[i].next)
102.         if(sz[e[i].to] > maxx && e[i].to != fx)
103.             maxx = sz[e[i].to] , hs[x] = e[i].to;
104. }
105. void dfs2(ll x , ll topV)
106. {
107.     idx[x] = ++tot;
108.     v[idx[x]] = val[x];
109.     top[x] = topV;
110.     if(!hs[x]) return;
111.     dfs2(hs[x],topV);
112.     for(int i = head[x] ; i ; i = e[i].next)
113.         if(e[i].to != f[x] && e[i].to != hs[x])
114.             dfs2(e[i].to , e[i].to);
115. }
116. inline void pushdown(ll node , ll ln , ll rn)
117. {
118.     if(tag[node])
119.     {
120.         tag[ls(node)] += tag[node] % p , tag[rs(node)] += tag[node] % p;
121.         tree[ls(node)] += tag[node] * ln % p, tree[rs(node)] += tag[node] * rn % p;
122.         tree[ls(node)] %= p , tree[rs(node)] %= p;
123.         tag[node] = 0;
124.     }
125. }
126. void build(ll l , ll r , ll node)
127. {
128.     if(l == r) {tree[node] = v[l];return;}
129.     ll m = l + r >> 1;
130.     build(l , m , ls(node));
131.     build(m + 1 , r , rs(node));
132.     pushup(node);
133. }
134. ll query(ll L , ll R , ll l , ll r , ll node)
135. {
136.     if(L <= l && r <= R) return tree[node];
137.     ll m = l + r >> 1 , ans = 0;
138.     pushdown(node , m - l + 1 , r - m);
139.     if(L <= m) ans += query(L , R , l , m , ls(node)) % p , ans %= p;
140.     if(R > m)  ans += query(L , R , m + 1 , r , rs(node)) % p , ans %= p;
141.     return ans;
142. }
143. void update(ll L , ll R , ll l , ll r , ll node , ll v)
144. {
145.     if(L <= l && r <= R)
146.     {
147.         tree[node] += (r - l + 1) * v % p , tree[node] %= p;
148.         tag[node] += v;
149.         return ;
150.     }
151.     ll m = l + r >> 1;
152.     pushdown(node , m - l + 1 , r - m);
153.     if(L <= m) update(L , R , l , m , ls(node) , v);
154.     if(R > m)  update(L , R , m + 1 , r , rs(node) , v);
155.     pushup(node);
156. }

简单叙述原理以及对时间复杂度的论述:

原理就是将树划分成重链轻链，然后通过适当的编号将重链接成序列用线段树维护，而由重儿子和轻儿子的定义可知，对于节点u的轻儿子v，

$sz[v]<=\frac{1}{2}sz[u]$

，这还是最最坏的情况下（均摊来讲要小得多）,最基本的放缩。

所以由这个显而易见的结论，我们还知道：

对于按轻重边划分有如下两条性质：

1.对于轻边(u,v)，

$size(v)<=size(u)/2$

2.对于从根到某一点的路径，轻边数不超过

$O(logn)$

重链数不超过

$O(logn)$

对性质1进行证明：

设u有k个子节点，分别为

$v1,v2,...，vk$

设

$(u,v1)$

为重边，则其余

$(u,vi)(i>1)$

为轻边。

$size(u)=size(v1)+size(v2)+...+size(vk)+1$

(其中k>=2，因为若k=1,则该边必为重边，即不含轻边)

$size(v1)>=size(vi)(i>1)$ $size(vi)+size(vi)=2∗size(vi)<=size(vi)+size(v1)<=size(u)$

即

$size(vi)<=size(u)/2$

对性质2进行证明:

设从root到v的路径中有k条轻边:

$root−>v1−>v2−>vk−>vroot−>...−>v1−>...−>v2−>...−>vk−>...−>v$

(其中

$−>v1,−>v2,...,−>vk−>v1,−>v2,...,−>vk$

为轻边)

$size(vk)>=size(v)>=1$ $size(vk的前趋)>=2∗size(vk)(性质1)>=2$

同理可得：

$size(vk−1的前趋)>=2∗size(vk的前趋)>=22size(vk−1的前趋)>=2∗size(vk的前趋)>=2^2$

所以有：

$n=size(root)>=size(v1的前趋)>=2kn=size(root)>=size(v1的前趋)>=2^k$

所以

$k=O(logn)$

从root到v的路径中有k条轻边，那么路径上其他边即为重边，那么重链数=k+1，所以重链数=O(logn)。

从上面的阐述中我们也可以理解到为什么树链剖分的常数那么小，因为很显然每一步放缩都是在2个节点并且是在轻重儿子最接近的情况下得出的结论。

我们看一道树剖的基础题

[HAOI2015]树上操作

题目描述

有一棵点数为 N 的树，以点 1 为根，且树点有点权。然后有 M 个操作，分为三种：操作 1 ：把某个节点 x 的点权增加 a 。操作 2 ：把某个节点 x 为根的子树中所有点的点权都增加 a 。操作 3 ：询问某个节点 x 到根的路径中所有点的点权和。

输入输出格式

输入格式：

第一行包含两个整数 N, M 。表示点数和操作数。接下来一行 N 个整数，表示树中节点的初始权值。接下来 N-1 行每行两个正整数 from, to ，表示该树中存在一条边 (from, to) 。再接下来 M 行，每行分别表示一次操作。其中第一个数表示该操作的种类（ 1-3 ），之后接这个操作的参数（ x 或者 x a ）。

输出格式：

对于每个询问操作，输出该询问的答案。答案之间用换行隔开。

输入输出样例

输入样例#1：

输出样例#1：

1
2
3

6
9
13

说明

对于 100% 的数据， N,M<=100000 ，且所有输入数据的绝对值都不

会超过 10^6 。

显然只需要树剖部分功能，并且操作一只需要在线段树上单点修改即可（仅仅是常数优化）。

Code:

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#define ls(x) ((x)<<1)
#define rs(x) ((x)<<1|1)
#define pushup(x) tree[(x)] = tree[ls((x))] + tree[rs((x))]
#define maxn 100005
#define ll long long
ll n , m , head[maxn] , f[maxn] , cnt , id , idx[maxn] , dep[maxn] , hs[maxn] , sz[maxn] , top[maxn] , val[maxn] , v[maxn] , tree[maxn<<2] , tag[maxn<<2] ;
struct edge{
    ll next , to;
}e[maxn * 2];
inline void add(ll x , ll y)
{
    e[++cnt].next = head[x];
    e[cnt].to = y;
    head[x] = cnt;
}
void dfs1(ll x , ll fx)
{
    f[x] = fx;
    sz[x] = 1;
    dep[x] = dep[fx] + 1;
    ll maxx = -1;
    for(int i = head[x] ; i ; i = e[i].next)
        if(e[i].to != fx)
            dfs1(e[i].to , x) , sz[x] += sz[e[i].to];
    for(int i = head[x] ; i ; i = e[i].next)
        if(sz[e[i].to] > maxx && e[i].to != fx)//attention : e[i].to != fx
            maxx = sz[e[i].to] , hs[x] = e[i].to;

}
void dfs2(ll x , ll topv)
{
    idx[x] = ++id;
    // printf("id = %d\n",idx[x]);
    top[x] = topv ;
    v[idx[x]] = val[x];
    if(!hs[x])  return;
    dfs2(hs[x],topv);
    for(int i = head[x] ; i ; i = e[i].next)
        if(e[i].to != hs[x] && e[i].to != f[x])
            dfs2(e[i].to , e[i].to);
}
inline void pushdown(ll node , ll ln , ll rn)
{
    if(tag[node])
    {
        tag[ls(node)] += tag[node]  , tag[rs(node)] += tag[node];
        tree[ls(node)] += tag[node] * ln , tree[rs(node)] += tag[node] * rn;
        tag[node] = 0;
    }
}
void build(ll l , ll r , ll node)
{
    if(l == r) {tree[node] = v[l];return;}
    ll m = l + r >> 1;
    build(l , m , ls(node));
    build(m + 1 , r , rs(node));
    pushup(node);
}
ll query(ll L , ll R , ll l , ll r , ll node)
{
    if(L <= l && r <= R) return tree[node];
    ll m = l + r >> 1 , ans = 0;
    pushdown(node , m - l + 1 , r - m);
    if(L <= m) ans += query(L , R , l , m , ls(node)) ;
    if(R > m)  ans += query(L , R , m + 1 , r , rs(node));
    return ans;
}
void update(ll L , ll R , ll l , ll r , ll node , ll v)
{
    if(L <= l && r <= R)
    {
        tree[node] += (r - l + 1) * v;
        tag[node] += v;
        return ;
    }
    ll m = l + r >> 1;
    pushdown(node , m - l + 1 , r - m);
    if(L <= m) update(L , R , l , m , ls(node) , v);
    if(R > m)  update(L , R , m + 1 , r , rs(node) , v);
    pushup(node);
}
ll qLink(ll x , ll y)
{
    ll ans = 0;
    while(top[x] != top[y])
    {
        if(dep[top[x]] < dep[top[y]]) std::swap(x,y);
        ans += query(idx[top[x]] , idx[x] , 1 , n , 1) ;
        x = f[top[x]];
    }
    if(dep[x] < dep[y]) std::swap(x,y);
    ans += query(idx[y],idx[x],1,n,1);
    return ans;
}
int main()
{
    scanf("%lld%lld",&n,&m);
    for(int i = 1; i <= n; ++i)
        scanf("%lld",&val[i]);
    ll x , y , d;
    for(int i = 1 ; i <= n-1; ++i)
        scanf("%lld%lld",&x,&y) , add(x,y) , add(y,x);
    dfs1(1,1);
    // puts("ok");
    dfs2(1,1);
    // puts("ok");
    build(1,n,1);
    // puts("ok");
    for(int i = 1 ; i <= m ; ++i)
    {
        int op;
        scanf("%d",&op);
        if(op == 1)
        {
            scanf("%lld%lld",&x,&d);
            update(idx[x],idx[x],1,n,1,d);
        }
        else if(op == 2)
        {
            scanf("%lld%lld",&x,&d);
            update(idx[x] , idx[x] + sz[x] - 1 , 1 , n , 1 , d);
        }
        else{
            scanf("%lld",&x);
            printf("%lld\n",qLink(1,x));
        }
    }
}

上午模拟赛我最后40分钟去还水了100分（雾

貌似300分的题随便拿280 ，然而剩下20分是什么仙人掌倍增？？

我们来看看T2与T3

1538124982665 样例输入 1
5 4 2
1 2 1
1 3 1
2 4 1
2 5 1
3 5
2 1

样例输出 1
3
1

样例输入 2
5 5 2
1 2 1

2 1 1
1 3 1
2 4 1
2 5 1
3 5
2 1

样例输出 2
3
1

样例输入 3
9 10 2
1 2 1
1 4 1
3 4 1
2 3 1
3 7 1
7 8 2
7 9 2
1 5 3
1 6 4
5 6 1
1 9
5 7

样例输出 3
5
6

1538125041691

作为一道0.1秒时限的题，显然中间的80分比较好拿。

算法一：用 SPFA 对每个点求一次单源最短路，由于是稀疏图，所以一次 SPFA 的复杂度
O(M)。然后 O(1)回答询问。
时间复杂度：

$O(NM)$

期望得分：10 分。

算法二：树上倍增法求 LCA。
这个是经典必备算法，不再赘述。
于是再算一下根到每个点的距离，于是就是

$dis[x]+dis[y]-2*dis[LCA(x,y)]$

。
啥？这个算法你不知道= =？如果想进省队的话，你赶紧去学吧>_<
时间复杂度：

$O((N+Q)logN)$

期望得分：40 分。

算法三：内向树上倍增法求 LCA 并计算路径长度。
先写个 DFS 找出来环，然后随便找环上一个点 P，顺时针遍历一遍环，求出环上各个点逆
时针走到它的距离。还可以顺便求出环长 len。
按照算法二的思路，倍增到环上之后，无非就有两种走法：继续走到 LCA、走环上另一边
的路径。前者 dfs 找环遍历时求过的，两个点逆时针到 P 的距离之差的绝对值，记为 dis，
后者就是 len-dis，这两个取 min 就好了。
时间复杂度：

$O((N+Q)logN)$

；期望得分：80 分。

*算法四：SPFA+仙人掌上倍增法求 LCA。
先 DFS 找环，顺便求环长神马的，这个跟算法三一样。
然后找个根节点，跑一遍 SPFA 求单源最短路。。。
在得到的单源最短路树上构建倍增数组。。。
于是剩下的就跟算法三一样了……倍增时走到最后，如果到了环上类似处理就好了。
时间复杂度：O((N+Q)logN)；期望得分：100 分。
另外，算法四是去年国家集训队 2011 作业，杨天的题，有详细证明和题解，Bzoj 上也有。
前面三个算法都是弱化版，因为作为 noip 题，算法四仅占 10%的分数。